#include <iostream>
using namespace std;
constexpr int MAX_ML = 100, MAX_MD = 100, MAXN = 100, INF = 1 << 30;
int N, ML, MD;
int AL[MAX_ML], BL[MAX_ML], DL[MAX_ML];
int AD[MAX_MD], BD[MAX_MD], DD[MAX_MD];
int d[MAXN];
bool updated;

void update(int &x, int y) {
    if (x > y) {
        x = y;
        updated = true;
    }
}

void bellmanford() {
    for (int k = 0; k <= N; k++) {
        updated = false;
        for (int i = 0; i + 1 < N; i++)
            if (d[i + 1] < INF) update(d[i], d[i + 1]);
        for (int i = 0; i < ML; i++)
            if (d[AL[i] - 1] < INF) update(d[BL[i] - 1], d[AL[i] - 1] + DL[i]);

        for (int i = 0; i < MD; i++)
            if (d[BD[i] - 1] < INF) update(d[AD[i] - 1], d[BD[i] - 1] - DD[i]);
    }
}

void solve() {
    fill(d, d + N, 0);
    bellmanford();
    if (updated) {
        cout << -1 << endl;
        return;
    }

    fill(d, d + N, INF);
    
    d[0] = 0;
    bellmanford();
    int res = d[N - 1];
    if (res == INF) res = -2;
    cout << res << endl;

}